package com.wm.algorithm.heap;

/**
 * @ClassName: MediumHeap
 * @Description: 中等级堆
 * @Author: WM
 * @Date: 2023/11/15 15:51
 */
public class MediumHeap {

    public static void main(String[] args) {
        int[] arr = new int[]{9, 3, 7, 6, 5, 1, 10, 2};
        System.out.println("原数组：");
        print(arr);
        int[] res = findTopN(arr, 5);
        System.out.println();
        System.out.println("现数组：");
        print(res);
    }

    private static void print(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            System.out.print("\t");
        }
    }

    /**
     * 从1亿个数字中取出最大的k个数字
     * 方法：堆排序
     * 思路：如果是内存有限制要求的话，使用堆排序，因为直接将1亿个数据加载到内存中会非常消耗内存，
     * 此时使用堆排序，建立k大小的小顶堆，然后依次取出剩余的数据，每取一个数据和堆顶元素进行比较，大于堆顶元素，
     * 则替换堆顶元素，小于堆顶元素直接舍弃。
     *
     * @param data
     * @param n
     */
    public static int[] findTopN(int[] data, int n) {
        // 首先构建n个数的小顶堆、
        buildHeap(data, n);
        // 遍历n个数后面的元素进行调整
        for (int i = n; i < data.length; i++) {
            adjust(data, i, n);
        }
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = data[i];
        }
        return res;
    }

    // 构建堆
    private static void buildHeap(int[] data, int n) {
        for (int i = 1; i < n; i++) {
            int t = i;
            int parentIndex = parent(t);
            while (t != 0 && data[parentIndex] > data[t]) {
                // 子节点比父节点小就交换位置
                int temp = data[t];
                data[t] = data[parentIndex];
                data[parentIndex] = temp;
                t = parentIndex;
                parentIndex = parent(t);
            }
        }
    }

    // 调整堆
    private static void adjust(int[] data, int i, int n) {
        // 判断堆顶元素和当前传入元素大小，如果当前元素比堆顶元素还小直接舍弃
        if (data[0] >= data[i]) {
            return;
        }
        // 调整堆大小，将当前元素直接放到堆首部，然后从上到下进行调整
        int temp = data[i];
        data[i] = data[0];
        data[0] = temp;
        // 调整堆顶 下层和当前层的判断
        int t = 0, leftIndex = left(t), rightIndex = right(t);
        while ((leftIndex < n && data[leftIndex] < data[t])
                || (rightIndex < n && data[rightIndex] < data[t])) {
            // 同层进行判断
            if (leftIndex < n && data[leftIndex] < data[rightIndex]) {
                // 左子节点更小直接置换
                temp = data[t];
                data[t] = data[leftIndex];
                data[leftIndex] = temp;
                t = leftIndex;
                leftIndex = left(t);
            } else {
                temp = data[t];
                data[t] = data[rightIndex];
                data[rightIndex] = temp;
                t = rightIndex;
                right(t);
            }
        }
    }

    // 父节点
    private static int parent(int index) {
        return (index - 1) / 2;
    }

    // 左子节点
    private static int left(int index) {
        return 2 * index + 1;
    }

    // 右子节点
    private static int right(int index) {
        return 2 * index + 2;
    }
}
